/**********************************************************************
Compile : gcc -O3 -o redundant redundant.c
Usage : ./redundant N L filename
N     : number of the nodes
L     : number of the steps
**********************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#define N_MAX 1000000

void print_help ()
{
	printf ("Usage         : ./redundant N L filename\n");
	printf ("                (./redundant 6 7 N-6x7-D)\n");
	printf ("N             : number of the nodes\n");
	printf ("L             : number of the steps\n");
	printf ("filename      : input feasible processes\n");
}

struct comment {
	int index;
	char buf[256];
} comment[N_MAX];

int compare (struct comment *p1, struct comment *p2)
{
	return strcmp (p1->buf, p2->buf);
}

/* Return 0/1 : 1 pathway1 is the same as pathway2 */
int check_redundant (int N, int L, int pathway1[L][N], int pathway2[L][N])
{
	int i, j, k, flag1, flag2, select[N];

	for (i = 0; i < N; i++)
	{
		select[i] = 0;
	}

	for (i = 0; i < N; i++)
	{
		flag2 = 0;
		for (j = 0; j < N; j++)
		{
			if (select[j] == 1)
				continue;

			flag1 = 0;
			for (k = 0; k < L; k++)
			{
				if (pathway1[k][i] != pathway2[k][j])
				{
					flag1 = 1;
					break;
				}
			}
			if (flag1 == 0)
			{
				flag2 = 1;
				select[j] = 1;
				break;
			}
		}
		if (flag2 == 0)
			return 0;
	}
	return 1;
}

void print_pathway (int N, int L, char comment[256], int pathway[L][N])
{
	int i, j, k;

	printf ("%s", comment);
	for (j = 0; j < L; j++)
	{
		for (k = 0; k < N; k++)
		{
			printf ("%d ", pathway[j][k]);
		}
		printf ("\n");
	}
}

int main (int argc, char *argv[])
{
	FILE *fp;
	char buf[256];
	int N, L;

	if (argc == 1)
	{
		print_help ();
		exit (0);
	}

	N = atoi (argv[1]);
	L = atoi (argv[2]);

	int i, j, k, n, p, pathway[N_MAX][L][N];

	fp = fopen (argv[3], "r");
	n = 0;
	while (fgets (comment[n].buf, 256, fp))
	{
		for (i = 0; i < L; i++)
		{
			for (j = 0; j < N; j++)
			{
				fscanf (fp, "%d", &pathway[n][i][j]);
			}
			fgets (buf, 256, fp);
		}
		n++;
	}
	fclose (fp);

	for (i = 0; i < n; i++)
	{
		comment[i].index = i;
	}

	qsort (comment, n, sizeof (struct comment), compare);

	int begin, end;

	for (i = 0; i < n; i++)
	{
		begin = i;
		for (end = begin + 1; end < n; end ++)
		{
			if (strcmp (comment[begin].buf, comment[end].buf) != 0)
				break;
		}
		i = end - 1;

		if (begin != i)
		{
			for (j = begin; j < end; j++)
			{
				int flag;

				flag = 1;
				for (k = begin; k < j; k++)
				{
					if (check_redundant (N, L, pathway[comment[j].index], pathway[comment[k].index]) == 1)
					{
						flag = 0;
						break;
					}
				}
				if (flag == 1)
					print_pathway (N, L, comment[j].buf, pathway[comment[j].index]);
			}
		}
		else
			print_pathway (N, L, comment[i].buf, pathway[comment[i].index]);
	}
}
